1. Field of the Invention
The present invention relates to an encoder and a decoder relating to an iterated transformation coding system.
2. Description of the Related Art
Recently, in communication systems and various information processing systems, the need to treat image data has increased, and it is important to develop techniques for transmitting or storing image signals with high performance and efficiency. Statistically, an image signal includes redundant components. By removing the redundant components, data for expressing the image signal can be compressed.
Various coding systems for reducing the proportion of redundancy of image have been proposed. The most important system, from the fundamental and practical viewpoint, is a transformation coding system. In the meantime, a returned transformation coding system has recently been reported under the name of "ITT (Iterated Transformation Theory)-based coding" in an academic society (Arnaud E. Jacquin "A NOVEL FRACTAL BLOCK-CODING TECHNIQUE FOR DIGITAL IMAGE", ICASSP'90 M8.2 1990 IEEE).
This coding system is characterized in that an original image is divided into a predetermined number of regions, and an image most similar to the image of the divided region is searched from transformed images obtained by subjecting the images of the regions different from the divided region to transformation (e.g. compression, rotation). The selected transformed image is changed to a code word, thereby compressing the image. In other words, this coding system is based on self-similarity, that is, this system is based on a fact that the image similar to each of the divided images of divided regions of an original image exists in divided regions different from the above divided region. In this context, the fact that a divided image A and a divided image B are similar to each other means that, in a three-dimensional space defined by an image plane (x, y) and a pixel value axis perpendicular to the image plane, there is a transformation capable of making the image curve surfaces of two divided images A and B coincide with each other. Specifically, the image curve surface of divided image A can be made to coincide with that of divided image B by suitable transformation such as reduction or rotation.
Hereinafter, the divided region of the original divided image to be transformed is referred to as "to-be transformed image region", the original divided image of the to-be-transformed i "to-be-transformed image" (image A in the above example), the region of the original divided image is "to-be-coded region", and the original image of this to-be-coded region is "to-be-coded image" (image B in the above example). The coding information in this coding system includes a transform method, to-be-transformed region, and to-be-coded region. According to this coding system, transform methods are designated to all images of partial regions obtained by dividing one frame. Thus, a code word representing each of the divided images of one frame includes information relating to the method of dividing a frame, transform method, to-be-transformed region and to-be-coded region. The information relating to the to-be-coded region, however, can be omitted by predetermining the method of dividing the frame, numbering the divided regions sequentially, and arranging coding information according to the sequential numbers.
In the aforementioned report, an original image is divided into a plurality of blocks each including 8.times.3 pixels, the to-be-coded region has 8.times.3 pixels or 4.times.4 pixels, and the to-be-transformed region is a square with one side having double the pixels of one side of the to-be-coded region, i.e. with 16.times.16 pixels or 8.times.8 pixels. As the transform method, the following are employed singly or in combination: a transformation for equalizing the number of pixels of a to-be-transformed region to that of a to-be-coded region, a transformation for multiplying the pixel value by a fixed number, a transformation for adding a fixed number to the pixel value, a transformation for setting the pixel value to a fixed value, a positional transformation for rotating the pixels of a to-be-transformed region by a unit of 90.degree., and a transformation for exchanging the pixels of a to-be-transformed region in a line-symmetrical manner. As a code word, there is employed information on a transform method for minimizing an error between a to-be-coded image and a transformed image obtained by subjecting the to-be-coded image to the above transformation.
On the other hand, in a decoding operation, an initial frame divided similarly with an original image is first employed. An image of the initial frame is, for example, an entirely black image. Then, the regions of the frame are converted according to coding words, thereby changing the pixel values. A resultant frame is called "first iterated frame." In this case, the regions of the first returned frame are converted not sequentially, but simultaneously.
By simultaneously converting all the regions of the first iterated frame, a second iterated frame is produced. Similar transformations are repeated, and the initial frame becomes gradually closer to the coded original image. When the returned frame has become close to the original image to a certain extent, the pixel values are no more changed by the transformations and the returned frame does not become close to the original image any more. The returned frame at this time is treated as a decoded image. The decoded image obtained by the above iterated transformation operation is definitely determined in relation to one transformation. In the aforementioned report, an eighth iterated frame is employed as a decoded image.
This coding system is advantageous in that the texture of the original image appears on the decoded image with higher fidelity, than in other coding systems such as a predictive coding system, transform coding system, vector quantization coding system, etc. However, an encoder and a decoder for working the above coding system have not been realized, and realization thereof has been demanded. In the iterated transformation system according to the above report, the shape of the to-be-coded region is limited to a square shape, and also the shape of the to-be-transformed region is limited to a square with one side having double the dimension of one side of the to-be-coded region. Consequently, the number of candidates for a to-be-transformed region similar to a to-be-coded region is small, and the decoded image is not necessarily close to the original image sufficiently, despite the fact that the number of codes is large. As a result, the coding efficiency is degraded.